package LeetCode._05_堆;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class _451_根据字符出现频率排序 {
    public String frequencySort(String s) {
        if(s == null) return null;
        Map<Character,Integer> count = new HashMap<>(); //键存放每个字符，值存放每个字符出现的次数
        for(char c : s.toCharArray()){
            //getOrDefault:该Key是否存在，如果不存在就是0，如果存在就返回对应的value
            count.put(c,count.getOrDefault(c,0) + 1);
        }
        //构造一个最大堆，存放的是Map的节点entry,按照值，大的在上面
        PriorityQueue<Map.Entry<Character,Integer>> maxHeap = new PriorityQueue<>((o1,o2) -> o2.getValue() - o1.getValue());
        maxHeap.addAll(count.entrySet()); //将所有节点加入堆中，自动进行原地建堆，最大堆
        StringBuilder sb = new StringBuilder();
        while(!maxHeap.isEmpty()){
            Map.Entry<Character, Integer> item = maxHeap.poll(); //取出堆顶元素
            char key = item.getKey(); //字符
            int val = item.getValue(); //字符出现次数
            for(int i= 0;i<val;++i){
                sb.append(key);
            }
        }
        return sb.toString();
    }
}
